package com.zhugang.week05;

/**
 * @program algorithms
 * @description: getIntersectionNode
 * @author: chanzhugang
 * @create: 2022/07/08 11:55
 */
public class IntersectionNode {

    /**
     * 160 相交链表
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 计算两个链表的长度，长的链表先走 a - b 步，再一起走
        ListNode lA = headA;
        int lengthA = 0;
        while (lA != null) {
            lengthA++;
            lA = lA.next;
        }
        ListNode lB = headB;
        int lengthB = 0;
        while (lB != null) {
            lengthB++;
            lB = lB.next;
        }

        lA = headA;
        lB = headB;
        if (lengthA > lengthB) {
            for (int i = 0; i < lengthA - lengthB; i++) {
                lA = lA.next;
            }
        } else {
            for (int i = 0; i < lengthB - lengthA; i++) {
                lB = lB.next;
            }
        }

        while (lA != null && lB != null && lA != lB) {
            lA = lA.next;
            lB = lB.next;
        }
        if (lA == null || lB == null) {
            return null;
        }
        return lA;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}